package algorithm_pattern

//在 pat 匹配 txt 的过程中，只要明确了「当前处在哪个状态」和「遇到的字符是什么」这两个问题，就可以确定应该转移到哪个状态（推进或回退）。
//dp[j][c] = next 表示，当前是状态 j，遇到了字符 c，应该转移到状态 next。
type KMP struct {
	dp  [][]int
	pat string
}

func CreateKMP(pat string) {
	M := len(pat)
	kmp := &KMP{}
	kmp.dp = make([][]int, M)
	// dp[状态][字符]=下个状态
	for i := range kmp.dp {
		kmp.dp[i] = make([]int, 256)
	}

	patBytes := []byte(pat)

	//base care
	first := patBytes[0]
	kmp.dp[0][first] = 1

	//影子状态，初始值为0
	X := 0
	//构建状态转移图
	for j := 1; j < M; j++ {
		charAt := patBytes[j]
		for c := 0; c < 256; c++ {
			kmp.dp[j][c] = kmp.dp[X][c]
			kmp.dp[j][charAt] = j + 1
		}
		//更新影子状态
		X = kmp.dp[X][charAt]
	}
}

func (kmp *KMP) Search(txt string) int {
	M := len(kmp.pat)
	N := len(txt)

	patBytes := []byte(kmp.pat)

	//pat的初始状态
	j := 0
	for i := 0; i < N; i++ {
		//计算pat的下一个状态
		j = kmp.dp[j][patBytes[i]]
		//到达终止态，返回结果
		if j == M {
			return i - M + 1
		}
	}

	//没有到达终止态，匹配失败
	return -1
}
